package LeetCode._05_堆;

import java.util.*;

public class _347_前K个高频元素 {
    public int[] topKFrequent(int[] nums, int k) {
        if(nums == null || nums.length == 0) return new int[0];
        Map<Integer,Integer> map = new HashMap<>();
        //按照每个元素出现次数的频率比较，存放出现次数前K大的元素,最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>((o1,o2) -> map.get(o1) - map.get(o2));
        for(int num : nums){ //统计每个元素出现次数的频率
            map.put(num,map.getOrDefault(num,0) + 1);
        }

        //遍历map的节点
        for(Map.Entry entry : map.entrySet()){
            Integer key = (Integer) entry.getKey();
            Integer value = (Integer) entry.getValue();
            if(minHeap.size() < k){ //先放前K个
                minHeap.offer(key);
            }else if(value > map.get(minHeap.peek())){ //如果当前key的出现频率大于当前最小堆中的堆顶元素
                minHeap.remove();
                minHeap.offer(key);
            }
        }
        int[] res = new int[minHeap.size()];
        int i =0;
        while(!minHeap.isEmpty()){
            res[i++] = minHeap.poll();
        }
        return res;
    }
}
